package com.zyk.grate_offer.class04;

import com.zyk.util.ArrayUtil;

/**
 * 返回一个数组中，选择的数字不能相邻的情况下，
 * 最大子序列累加和
 *
 * @author zhangsan
 * @date 2021/4/28 16:58
 */
public class Code04_SubArrayMaxSumFollowUp {

    public static int subSqeMaxSumNoNext(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        if (arr.length == 1) {
            return arr[0];
        }
        return process(arr, 0);
    }

    private static int process(int[] arr, int i) {
        if (i >= arr.length) return 0;
        int p1 = arr[i] + process(arr, i + 2);
        int p2 = process(arr, i + 1);
        return Math.max(p1, p2);
    }

    // 改动态规划
    public static int dp(int[] arr) {
        int N;
        if (arr == null || (N = arr.length) == 0) return 0;
        if (N == 1) return arr[0];
        int[] dp = new int[N + 2];
        for (int i = N - 1; i >= 0; i--) {
            int p1 = arr[i] + dp[i + 2];
            int p2 = dp[i + 1];
            dp[i] = Math.max(p1, p2);
        }
        return dp[0];
    }

    // 改动态规划
    public static int dp2(int[] arr) {
        int N;
        if (arr == null || (N = arr.length) == 0) return 0;
        if (N == 1) return arr[0];
        int a = 0, b = 0, c = 0;
        for (int i = N - 1; i >= 0; i--) {
            c = Math.max(arr[i] + a, b);
            a = b;
            b = c;
        }
        return c;
    }

    public static int subSqeMaxSumNoNext2(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        if (arr.length == 1) {
            return arr[0];
        }
        int[] dp = new int[arr.length];
        // dp[i] : arr[0..i]挑选，满足不相邻设定的情况下，随意挑选，最大的累加和
        dp[0] = arr[0];
        dp[1] = Math.max(arr[0], arr[1]);
        for (int i = 2; i < arr.length; i++) {
            int p1 = dp[i - 1];
            int p2 = arr[i] + Math.max(dp[i - 2], 0);
            dp[i] = Math.max(p1, p2);
        }
        return dp[arr.length - 1];
    }

    // for test
    public static void main(String[] args) {
        int[] arr = ArrayUtil.generateRandomArray(10, 100);
        int[] arr2 = ArrayUtil.copyArr(arr);
        System.out.println(subSqeMaxSumNoNext(arr));
        System.out.println(subSqeMaxSumNoNext2(arr2));
        System.out.println(dp(arr));
        System.out.println(dp2(arr));
    }

}
